1. Field of the Invention
The present invention relates to an encryption operating apparatus and method having side-channel attack resistance, which is secure with respect to analysis of a secret key in an encryption processor using side-channel attack and is capable of conducting operation processing with respect to decoding processing at a high speed.
2. Description of the Related Art
Due to the recent development of a computer network, chances of searching for a database and transmitting/receiving electronized information such as electronic mail and electronic news via a network are increasing rapidly. Furthermore, service such as on-line shopping is being provided using the network.
However, as service involving transfer of money is increased, a new problem such as an increase in so-called network crime (tapping and tampering of electronized data on a network, enjoying service by pretending to be another person, etc.) has been pointed out. Particularly in a wireless network environment, it is easy to intercept communication, so that there is a great demand for measures for preventing such an act in particular.
In order to solve the above-mentioned problem, encrypted electronic mail using an encryption technology, a user authentication system using an electronic signature, etc. have been proposed and are being introduced into various networks. In view of this, an encryption technology or an electronic signature generation technique is considered as one of indispensable techniques in a computer network environment.
Along with the advancement of such an encryption technology or an electronic signature generation technique, a method for attacking it is also being advanced rapidly. For example, side-channel attack is an attack method for measuring a processing time and a power consumption of an encryption processor, and analyzing a secret key of a code based on the features of the measured processing time and power consumption. Typically, timing attack or SPA (Simple Power Analysis) are known.
If the timing attack or SPA is used for an encryption scheme containing a remainder operation, the relationship in magnitude between an input value and a remainder value can be determined, so that it is possible to know the remainder value (i.e., the value of a secret key) by conducting a binary search while manipulating the input value.
More specifically, it is determined based on an input value whether or not a remainder operation is conducted, and there is a large difference in processing time and power consumption between the case where a remainder operation is conducted and the case where a remainder operation is not conducted. Therefore, it is possible to determined the relationship in magnitude between the input value and the remainder value by conducting timing attack paying attention to the difference in processing time and SPA paying attention to the difference in power consumption required for an operation.
Therefore, if an attacker (malicious third party) uses the above-mentioned attack method, the third party can reveal the remainder value that is unknown to the third party by repeating a binary search while manipulating an input value. This implies that the third party can know a remainder value that is a secret key, for example, in the case where RSA with Chinese remainder theorem is used, which is considered to be fatal to the security in the encryption technology.
The attack method as described above is also applicable to generation processing of an electronic signature. More specifically, if key information at a time of generation of an electronic signature is analyzed by a third party, the third party can generate the electronic signature arbitrarily, which enables the third party other than a user to easily pretend to be the user. Thus, this fact is considered to be fatal to the security introducing an electronic signature.
Hereinafter, decoding of a code will be exemplified specifically by using numerical expressions. First, the processing of RSA decoding using a general Chinese remainder theorem can be expressed as follows:Xp=X mod pXq=X mod qYp=Xpdp mod pYq=Xqdq mod qY=(a(Yq−Yp)mod q)p+Yp  (1)                where a=p−1 mod q                    dp=d mod(p−1)            dq=d mod(q−1)                        
In Expression 1, d, p, and q represent secret keys, and plaintext Y corresponding to ciphertext X is obtained by Y=Xdmod N (N=pq). By using modular exponentiation operations Yp and Yq as in Expression 1, the processing time can be shortened to about ¼ compared with the method of directly obtaining Xdmod N.
When the remainder value p is paid attention to, and an arbitrary input X is input to the first expression Xp=X mod p in Expression 1, it is determined whether or not a remainder operation is conducted based on the relationship in magnitude between X and p. More specifically, in the case of X≧p, a remainder operation of X mod p is conducted, and in the case of X<p, a remainder operation is not conducted.
Thus, in the case of using the timing attack, the relationship in magnitude between X and p is determined based on the length of an operation time. That is, in the case where X (X≧p) is input, a remainder operation is conducted, so that the operation time becomes long. On the other hand, in the case where X (X<p) is input, a remainder operation is not conducted, so that the operation time becomes short.
In the case where the operation time is long, a value smaller than X (which has been input) is input, and in the case where the operation time is short, a value larger than X is input. Then, an operation time is measured again. By repeating such processing, an input value X matched with the remainder value p can be obtained finally, which makes it possible to reveal the secret key p.
In the case of using the SPA, the relationship in magnitude between X and p is determined based on the difference in waveform of a power consumption obtained by an operation. More specifically, as shown in FIGS. 1A–1C, assuming that a waveform of a power consumption by an operation A that does not involve a remainder operation is shown in FIG. 1A, and a waveform of a power consumption by an operation B that involves a remainder operation is shown in FIG. 1B, it can be determined from a waveform shown in FIG. 1C of a measured power consumption whether or not the operation B involving a remainder operation has been conducted.
Accordingly, as shown in FIG. 1C, in the case where a waveform of a power consumption by the operation B involving a remainder operation is contained, it can be determined that the input X satisfies X≧p, and in the case where a waveform of a power consumption by the operation B involving a remainder operation is not contained, it can be determined that the input X satisfies X<p. Thus, in the same way as in the timing attack, in the case where a waveform of a power consumption by the operation B involving a remainder operation is contained, a value smaller than X (which has been input) is input, and in the case where a waveform of a power consumption by the operation B involving a remainder operation, a value larger than X is input. Then, a waveform of a power consumption is observed again. By repeating such processing, an input value X matched with the remainder value p can be obtained finally, which enables the secret key p to be revealed.
The input value X matched with the remainder value q can be obtained by using the attack method as described above to the secret key q in a similar manner. Therefore, it is also possible for the third party to know the secret key q.
Various techniques can be considered regarding a method for preventing these attacks. A typical method is to conduct a remainder operation after multiplying input data by a random number. Because of this, whether or not a remainder operation is conducted does not depend upon only the relationship in magnitude between the input data and the remainder value, and whether or not a remainder operation is conducted is determined randomly based on the magnitude of a random value. Therefore, irrespective of whether the timing attack is used or the SPA is used, the remainder value q or p (i.e., a secret key) cannot be revealed.
However, according to the above-mentioned method merely using multiplication of a random number, a considerable time is required for an operation of correction. More specifically, in order to conduct correction processing with respect to multiplication of a random number, it is required to derive an appropriate correction value. However, since a random number is used, it is required to derive a correction value every time a random number is multiplied. Because of this, an operation of deriving a correction value must be conducted every time, which results in a considerable time for operation processing.
For example, in the same way as in Expression 1, the processing of decoding ciphertext into plaintext with RSA using Chinese remainder theorem in the case of using a random number r can be expressed by Expression 2.Xp′=X*r mod pXq′=X*r mod qYp=Xp′dp mod pYq=Xq′dq mod qYp′=Yp*r−dP mod pYq′=Yq*r−dq mod qY′=(a(Yq′−Yp′)mod q)p+Yp′  (2)                where a=p−1 mod q                    dp=d mod(p−1)            dq=d mod(q−1)                        
In Expression 2, d, p, and q represent secret keys, and plaintext Y corresponding to ciphertext X is obtained by Y=Xdmod N (N=pq). By previously multiplying the input X by the random number r as in Expression 2, whether or not a remainder operation is conducted does not depend upon the relationship in magnitude between the input value X and the remainder value p or q. Unlike Expression 1, it is required to multiply the value of a remainder operation by a correction value r−dp mod p or r−dq mod q corresponding to each multiplied random number r. This results in an increase in number of operation processing by the time Xd mod N to be obtained finally is reached.